import java.util.ArrayList;
import java.util.List;

//扩展法
public class Demo {
    public List<List<Integer>> subsets(int[] nums){
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        for (int i: nums){
            List<List<Integer>> subset = new ArrayList<>();
            for(List<Integer> list: result){
                List<Integer> temp = new ArrayList<>(list);
                temp.add(i);
                subset.add(temp);
            }
            for(List<Integer> l: subset){
                result.add(l);
            }
        }
        return result;
    }
    //回溯法
    public List<List<Integer>> subsets2(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        for(int i = 1; i <= nums.length; i++){
            backtracking(nums, result, i, 0 ,new ArrayList<>());
        }
        return result;
    }
    private void backtracking(int[] nums, List<List<Integer>> result, int length, int index, List<Integer> subset){
        if(subset.size() == length){
            result.add(new ArrayList<>(subset));
            return;
        }
        for(int i = index; i < nums.length; i++){
            subset.add(nums[i]);
            backtracking(nums, result, length, i+1, subset);
            subset.remove(subset.size()-1);
        }
    }
    //深度优先算法
    public List<List<Integer>> subsets3(int[] nums){
        List<List<Integer>> result = new ArrayList<>();
        dfs(nums, result, 0, new ArrayList<>());
        return result;
    }
    private void dfs(int[] nums, List<List<Integer>> result, int index, ArrayList<Integer> subset) {
        result.add(new ArrayList<>(subset));
        if(nums.length == index){
            return;
        }
        for(int i = index; i < nums.length; i++){
            subset.add(nums[i]);
            dfs(nums, result, i+1, subset);
            subset.remove(subset.size()-1);
        }
    }
}


